import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class Merge extends Example {
    private static Comparable[] aux;
    public static void sort(Comparable[] a){
        aux = new Comparable[a.length];
        sort(a,0,a.length-1);
    }
    private static void sort(Comparable[] a,int lo,int hi){
        if(lo>=hi) return ;
        int mid = (lo+hi)/2;
        sort(a,lo,mid);
        sort(a,mid+1,hi);
        merge(a,lo,mid,hi);
    }
    public static void merge(Comparable[] a, int lo,int mid,int hi){
        StdOut.printf("merge(a,%d,%d,%d)\n",lo,mid,hi);
        int i = lo,j = mid +1;
        for(int k = lo;k<=hi;k++){
            aux[k] = a[k];
        }
        for(int k = lo; k <=hi; k ++){
            if( i>mid) a[k] = aux[j++];
            else if( j>hi) a[k] = aux[i++];
            else if(less(a[j],a[i])) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
        show(a);
    }

    public static void sortbu(Comparable[] a){
        int N = a.length;
        aux = new Comparable[N];
        for(int sz = 1;sz<N;sz+=sz){
            for(int lo = 0 ; lo<N-sz;lo+=sz+sz){
                merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1,N-1));
            }
        }
    }

//    public static void sortbu(Comparable[] a){
//        int N = a.length;
//        aux = new Comparable[N];
//        for(int sz = 2;sz<=N+1;sz+=sz){
//            StdOut.println(sz);
//            for(int lo = 0 ; lo<N;lo+=sz){
//                merge(a,lo,lo+(sz-1)/2,Math.min(lo+sz-1,N-1));
//            }
//        }
//    }

    public static void main(String[] args){
        String[] a = StdIn.readStrings();
        sortbu(a);
        assert isSorted(a);
    }
}

